#include "Heap.h"

void HeapInit(HP *hp)
{
    assert(hp);

    hp->p = NULL;
    hp->size = 0;
    hp->capacity = 0;
}

void HeapDestory(HP *hp)
{
    assert(hp);
    free(hp->p);
    hp->p = NULL;
    hp->size = 0;
    hp->capacity = 0;
}

void HeapPrint(HP *hp)
{
    assert(hp);

    for (size_t i = 0; i < hp->size; ++i)
    {
        printf("%d ", hp->p[i]);
    }
    printf("\n");
}

void Swap(HPDataType *a1, HPDataType *a2)
{
    HPDataType tmp = *a1;
    *a1 = *a2;
    *a2 = tmp;
}

void AdHeapUp(HPDataType *a, size_t child)
{
    //求父节点的下标
    size_t parent = (child - 1) / 2;
    //当向上调整到根节点([0])时，退出循环
    while (child > 0)
    {
        //当孩子节点小于父节点时进行调整，说明这是一个"小堆"->根节点存储最小的节点
        //当孩子节点大于父节点时进行调整，说明这是一个"大堆"->根节点存储最大的节点
        if (a[child] > a[parent]) //大堆
        // if (a[child] < a[parent])      //小堆
        {
            Swap(&a[child], &a[parent]);
            //更新子节点和父节点
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            //不符合条件就说明调整完毕，直接跳出循环
            break;
        }
    }
}

void HeapPush(HP *hp, HPDataType x)
{
    assert(hp);

    //判断容量是否已满，满了扩容
    if (hp->size == hp->capacity)
    {
        size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        HPDataType *sp = (HPDataType *)realloc(hp->p, sizeof(HPDataType) * newCapacity);
        //判空
        if (sp == NULL)
        {
            printf("realloc fail!!!\n");
            exit(EXIT_FAILURE);
        }
        hp->p = sp;
        hp->capacity = newCapacity;
    }

    //插入数据
    hp->p[hp->size] = x;
    ++hp->size;

    //向上调整，控制保持是一个小堆
    AdHeapUp(hp->p, hp->size - 1);
}

void AdJustDown(HPDataType *a, size_t root, size_t size)
{
    size_t parent = root;
    //左孩子下标位置
    size_t child = (parent * 2) + 1;

    //孩子节点大于最大节点时，就说明向下调整完毕，退出循环
    while (child < size)
    {
        //选出左右孩子中最小/大的那个->"小/大堆"
        //如果右孩子(a[child + 1])小于左孩子(a[child])
        //则最小的孩子是右孩子,自增一下左孩子下标就是右孩子了
        // if (a[child + 1] > a[child] && child + 1 < size) //大堆
        if (a[child + 1] < a[child] && child + 1 < size) //小堆
        {
            ++child;
        }

        //当孩子节点小于父节点时进行调整，说明这是一个"小堆"->根节点存储最小的节点
        //当孩子节点大于父节点时进行调整，说明这是一个"大堆"->根节点存储最大的节点
        if (a[child] < a[parent]) //小堆
        // if (a[child] > a[parent]) //大堆
        {
            //交换节点数据，并且继续往下调整
            Swap(&a[child], &a[parent]);
            //更新父节点下标和孩子节点下标
            parent = child;
            child = (parent * 2) + 1;
        }
        else
        {
            break;
        }
    }
}

//删除堆顶数据(最小/最大值)
void HeapPop(HP *hp)
{
    assert(hp);
    assert(hp->size > 0);

    //首先交换根节点和最后一个节点的数据
    Swap(&hp->p[0], &hp->p[hp->size - 1]);
    //除最后一个节点数据
    --hp->size;

    //向下调整堆
    AdJustDown(hp->p, 0, hp->size);
}

bool HeapEmpty(HP *hp)
{
    assert(hp);
    return hp->size == 0;
}

size_t HeapSize(HP *hp)
{
    assert(hp);
    assert(hp->size > 0);
    return hp->size;
}

size_t HeapTop(HP *hp)
{
    assert(hp);
    assert(hp->size > 0);

    return hp->p[0];
}

// //堆排序->时间复杂度O(n)
// void HeapSort(int *a, size_t n)
// {
//     //通过向下调整接口建立"大堆"
//     for (int i = (n - 1 - 1) / 2; i >= 0; --i)
//     {
//         AdJustDown(a, i, n);
//     }

//     //进行排序
//     size_t end = n - 1;
//     //当end等于0时，说明已经排序完成
//     while (end > 0)
//     {
//         //根节点与尾节点进行数据交换
//         Swap(&a[0], &a[end]);
//         //向下调整，保持根节点为最大值
//         AdJustDown(a, 0, end);
//         //忽略最后一个节点
//         --end;
//     }
// }

// int main()
// {
//     int Array[] = {1, 8, 4, 6, 5, 7, 9, 0, 2, 3};
//     //堆排序
//     HeapSort(Array, sizeof(Array) / sizeof(Array[0]));
//     for (int i = 0; i < sizeof(Array) / sizeof(Array[0]); ++i)
//     {
//         printf("%d ", Array[i]);
//     }
//     printf("\n");
//     system("pause");
// }

// TOP-K问题
void PrintTopK(int *a, int n, int k)
{
    // 1. 建堆--用a中前k个元素建堆
    int *Heap = (int *)malloc(sizeof(int) * k);
    assert(Heap);
    for (int i = 0; i < k; ++i)
    {
        Heap[i] = a[i];
    }
    //建小堆->向下调整
    for (int i = (k - 1 - 1) / 2; i >= 0; --i)
    {
        AdJustDown(a, i, k);
    }

    // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    for (int i = k; i < n; ++i)
    {
        if (Heap[0] < a[i])
        {
            Heap[0] = a[i];
            AdJustDown(Heap, 0, k);
        }
    }
    //进行排序
    int end = k - 1;
    while (end > 0)
    {
        Swap(&Heap[0], &Heap[end]);
        AdJustDown(Heap, 0, end);
        --end;
    }

    for (int i = 0; i < k; ++i)
    {
        printf("%d ", Heap[i]);
    }
    printf("\n");
}
void TestTopk()
{
    int n = 10000;
    int *a = (int *)malloc(sizeof(int) * n);
    srand(time(0));
    for (size_t i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;
    }
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[115] = 1000000 + 5;
    a[2335] = 1000000 + 6;
    a[9999] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;
    //排序前十个最大的数
    PrintTopK(a, n, 10);
}

int main()
{
    TestTopk();
    system("pause");
    return 0;
}